package 面试题07_重建二叉树;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 16:22 2021/2/3
 * @Description：
 */


import java.util.HashMap;
import java.util.Map;

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    // 用于在中序遍历序列中查找“根/父节点的索引位置
    Map<Integer, Integer> indexMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 检测是否为特殊输入测试
        if (preorder.length == 0 || inorder.length == 0 || preorder.length != inorder.length) {
            return null;
        }


        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }

        TreeNode root = buildTreeCore(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);

        return root;
    }

    TreeNode buildTreeCore(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd) {
        // 处理前序遍历中子树为0的情况
        if (preorderStart > preorderEnd) {
            return null;
        }

        // 根节点为前序遍历序列中的第一个值
        int rootValue = preorder[preorderStart];
        TreeNode root = new TreeNode(rootValue);

        // 终止条件：左/右子树的序列中只剩下一个值
//        if (preorderStart == preorderEnd) {
        // 这两个判断条件都可以！
        if (inorderStart == inorderEnd) {
            return root;
        } else {
            // 根据根节点在中序遍历中的位置确定左右子树各自的数量，以此来确定前序遍历中左右子树的区间范围
            int rootIndex_inorder = indexMap.get(rootValue);
            int leftNodes_count = rootIndex_inorder - inorderStart;
            int rightNodes_count = inorderEnd - rootIndex_inorder;
            TreeNode leftNode = buildTreeCore(preorder, preorderStart + 1, preorderStart + leftNodes_count, inorder, inorderStart, rootIndex_inorder - 1);
            //TreeNode rightNode = buildTreeCore(preorder, preorderStart + leftNodes_count + 1, preorderEnd, inorder, rootIndex_inorder + 1, inorderEnd);
            TreeNode rightNode = buildTreeCore(preorder, preorderEnd - rightNodes_count + 1, preorderEnd, inorder, rootIndex_inorder + 1, inorderEnd);

            root.left = leftNode;
            root.right = rightNode;

            return root;
        }


    }
}
